/*
 * bignum.c
 *
 *  Created on: Aug 20, 2011
 *      Author: diegolascasas
 */

#include "bignum.h"

void insereesquerda(bignum* x,int valor){ /*Sobe uma casa decimal*/
  x->inicio->prox->ant = malloc(sizeof(alg));      
  x->inicio->prox->ant->prox=x->inicio->prox;
  x->inicio->prox=x->inicio->prox->ant;
  x->inicio->prox->ant=x->inicio;
  x->inicio->prox->v=valor;
  x->tamanho++;
  /*printf("%i",x->ultima_casa->v);  /*DEBUG  /**/
} 

void inseredireita(bignum* x,int valor){ /*nao sobe casas decimais!*/
  x->ultima_casa->prox = malloc(sizeof(alg));
  x->ultima_casa->prox->ant = x->ultima_casa;
  x->ultima_casa=x->ultima_casa->prox;
  x->ultima_casa->v=valor;
  x->ultima_casa->prox=NULL;
  x->tamanho++;
  /*adicionar uma funcao para transformar tamanho em bignum caso ele seja maior que o maximo permitido para uma int?
  /*printf("%i",x->ultima_casa->v);  /*DEBUG  /**/
} 

void removeesquerda(bignum* x){
  x->inicio->prox=x->inicio->prox->prox;
  free(x->inicio->prox->ant);
  x->inicio->prox->ant=x->inicio; 
  x->tamanho--;
}

void limpacasas(bignum* x){
  while(x->inicio->prox->v==0)
    removeesquerda(x);
}


/*pensar em uma forma de substituir os numeros. /**/
void criar(bignum** big,char* numero){
  /*cria o bigum vazio /**/
  int i;
  bignum* x = malloc(sizeof(bignum));
  x->inicio= malloc(sizeof(alg)); /*cabeca /**/
  x->ultima_casa= x->inicio;
  x->inicio->v=0;
  x->tamanho=0;
  i=0;

  /*checa o sinal */
  if (numero[0]=='-'){
    x->inicio->v=1;
    i++;
  } 

  /*evita 0s a esquerda. O numero 0 eh um com tamanho=0. /**/
  while (numero[i]=='0')
    i++;
  
  /*printf("DEBUG: bignum lido = "); /**/

  /*aloca cada integra */
  for (i;i<strlen(numero);i++){
    /*if(numero[i]!=numero), erro. /**/
    int valor=(int)numero[i]-(int)'0';
    if (valor<0||valor>9)
      error("ERRO: entrada possui caracteres desconhecidos");

    inseredireita(x,valor);
  }
  
  /*IMPORTANTE: essa funcao usa um atalho para nao ter que ter duas celulas 
   * cabeca, uma no comeco e uma no fim.
   * O mais intuitivo seria inserir a esquerda comecando pelo ultimo algarismo.
   */
  /* printf("\n" ); /*DEBUG */
  
  *big=x;
}


void destruir(bignum* x){
  /*tem como cancelar se o numero nao aponta pra nada*/
  alg* p=x->inicio;
  alg* q;
  int i=0;
  for(i;i<=x->tamanho;i++){
    q=p;
    p=p->prox;
    free(q);
  }

  free(x);
}


void imprimir(bignum* x){
  int n=x->tamanho;
  /*printf("DEBUG: %i",n);  */
  int i=0;
  alg* p;
  if (n==0){
    printf("0");
    return;
      }
  p=x->inicio->prox;
  
  
  if (x->inicio->v==1)
    printf("-");
  for(i;i<n;i++){
    printf("%i",p->v);
    p=p->prox;
  }
}

/*checa se a é maior do que b*/
int maior(bignum* a, bignum* b){
  int i;
  alg *p,*q;
  if(b->tamanho==0){
    if(a->tamanho==0)
      return 0;
    return 1-a->inicio->v; /*1-1 caso a seja negativo, 1-0 caso positivo*/
  }

  if(a->inicio->v!=b->inicio->v) /*checa se os sinais sao iguais */
    if(b->inicio->v==1)
      return 1;

  if(a->tamanho>b->tamanho)
    return 1-a->inicio->v;

  if(a->tamanho==b->tamanho){
    p=a->inicio->prox;
    q=b->inicio->prox;
    for(i=0;i<a->tamanho;i++){
      if(p->v>q->v)
	return 1-a->inicio->v;
      if(p->v<q->v)
	return 0+a->inicio->v;
      p=p->prox;
      q=q->prox;
    }
  } 
      return (0+a->inicio->v);
}


void troca(bignum** a,bignum** b){
  bignum** aux;
  aux=malloc(sizeof(bignum**));
  *aux = *a;
  *a=*b;
  *b=*aux;
  free(aux);
}


void somar(bignum** x,bignum* a,bignum* b){
  int vai_um,i,n;
  alg *p,*q;

  if(b->inicio->v!=a->inicio->v){
    b->inicio->v=1-b->inicio->v;
    subtrair(x,a,b);
    return;
  }
  /*
  if ((*x)->tamanho!=0)    /*So no caso de x=0 que ele passa os dois prim. if
    destruir(*x);        
  */
  if (a->tamanho<b->tamanho){
    troca(&a,&b);         
  }
  if(b->tamanho==0){
    *x=a;
    return;
  }

  n=b->tamanho;
  
  p=a->ultima_casa;
  q=b->ultima_casa; 
  vai_um=0;
  for (i=0;i<n;i++){
    p->v+=q->v+vai_um;
    vai_um=0;
    if (p->v>9){
      p->v=p->v-10;
      vai_um=1;
    }
    p=p->ant;
    q=q->ant;
  }

  while (vai_um==1){
      p->v+=1;
      vai_um--;
	if(p->v>9){
	  p->v-=10;
	  vai_um++;
	}
      p=p->ant;
  }

  *x=a;
}


void subtrair(bignum** x,bignum* a,bignum* b){
  int empresta,i,n;
  alg *p,*q;
  /* o vai_um so joga unidades uma casa para frente. assume-se que a >= b*/

  if(b->inicio->v!=a->inicio->v){
    b->inicio->v=1-b->inicio->v;
    somar(x,a,b);
    return;
  }
  /*
  if ((*x)->tamanho!=0)    /*So no caso de x=0 que ele passa os dois prim.
    destruir(*x);        
  */

  if(maior(a,b)-a->inicio->v==0){
    troca(&a,&b); /* Se a<b no caso positivo ou a>b no caso negativo, troca. */ 
    a->inicio->v=1-a->inicio->v;
  }

  if(b->tamanho==0){
    *x=a;
    return;
  }

  n=b->tamanho;
  
  p=a->ultima_casa;
  q=b->ultima_casa; 
  empresta=0;
  for (i=0;i<n;i++){
    p->v= p->v - q->v - empresta; /*vou precisar dessa variavel no final*/
    empresta=0;
    if (p->v<0){
      p->v=p->v+10;
      empresta++;
    }
    p=p->ant;
    q=q->ant;
  }

  while (empresta==1){
      p->v-=1;
      empresta--;
	if(p->v<0){
	  p->v+=10;
	  empresta++;
	}
      p=p->ant;
  }

  limpacasas(a);
  *x=a;
}


